Binary Search 是一個搜尋演算法~ 它的時間複雜度只有O log(n)~

但使用它之前要先確認資料是已排序過的~

在使用迴圈將 target 與中間值比較，如 target 大於中間值，就往右搜尋~ 否則就往左搜尋~

學習目標: Binary Search的概念及實務

學習難度: ☆☆☆

#include <iostream>

#include <algorithm> //內建sort的library

using namespace std;

int BinarySearch(int array[],int length,int target)
{
	int start,end,mid;
	
	start=0;
	
	end=length-1;
	
	while(start<=end)
	{
		mid=(start+end)/2;
		
		if(array[mid]==target)
		{
			return ++mid;
		}
		else if(target>array[mid])
		{
			start=mid+1;
		}
		else if(target<array[mid])
		{
			end=mid-1;
		}
	}
}

int main()
{
	int array[8]={12,3,1,5,18,10,7,35};
	
	int length=sizeof(array)/sizeof(array[0]); /*array的長度是array的大小除以單一元素的大小*/
	
	sort(array,array+length); /*可以先用內建的sort，如果沒用其他排序*/
	
	int target=BinarySearch(array,length,7);
	
	cout<<target<<endl;
		
	return 0;
}

參考資料:

https://shengyu7697.github.io/cpp-binary-search/

https://www.google.com/search?q=binary+search+c%2B%2B&source=hp&ei=YqdRYvXZObCymAW0rL7oBQ&iflsig=AHkkrS4AAAAAYlG1cnO1ZSUym6ofO_RVje6d3oMkYtUZ&oq=Binary+Search&gs_lcp=Cgdnd3Mtd2l6EAEYAjIICAAQgAQQsQMyCAgAEIAEELEDMgUIABCABDIFCAAQgAQyBQgAEIAEMgUIABCABDIFCAAQgAQyBQgAEIAEMgUIABCABDIFCAAQgARQAFgAYO8HaABwAHgAgAE3iAE3kgEBMZgBAKABAqABAQ&sclient=gws-wiz